home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 1 / LSD Compendium Deluxe 1.iso / a / programming / assemblers / cas.lha / orig / link.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-10  |  14.6 KB  |  461 lines
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include "io.h"
  4. #include "ex.h"
  5. #include "res.h"
  6. #include "st.h"
  7.  
  8. typedef struct FileBuf *FileBuf;
  9. struct FileBuf {
  10.    char *Name;
  11.    long Loc, Files, Segs, Gaps, Syms, Exps, Relocs;
  12.    char **File; Segment Seg; Gap G; Symbol *Sym;
  13. };
  14. FileBuf FTab; int Fs;
  15.  
  16. typedef struct Block *Block;
  17. struct Block {
  18.    char *Src, *Obj; Segment Seg; Block Next;
  19. };
  20.  
  21. static Block *BHead;
  22. static int *BSize;
  23. static Segment USeg;
  24.  
  25. typedef struct Image *Image;
  26. struct Image {
  27.    word Base; long Size; char *Src, *Obj; word Line; long Loc;
  28.    Image Prev, Next;
  29. };
  30. static Image IHead, ITail;
  31.  
  32. Exp *ExpBuf;
  33.  
  34. static Image FormImage(
  35.    word Base, long Size, char *Src, char *Obj, word Line, long Loc
  36. ) {
  37.    Image IP = (Image)Allocate(sizeof *IHead);
  38.    IP->Base = Base, IP->Size = Size, IP->Src = Src, IP->Obj = Obj,
  39.    IP->Line = Line, IP->Loc = Loc;
  40.    return IP;
  41. }
  42.  
  43. static void SetImage(void) {
  44.    Block BP;
  45.    for (IHead = ITail = 0, BP = BHead[0]; BP != 0; BP = BP->Next) {
  46.       Segment Seg = BP->Seg; Image P, IP, NewI;
  47.       for (IP = IHead; IP != 0; IP = IP->Next)
  48.          if (IP->Base >= Seg->Base) break;
  49.       P = (IP == 0)? ITail: IP->Prev;
  50.       if (P != 0 && P->Base + P->Size > Seg->Base)
  51.          FATAL("Overlapping segments at [%d] %s and [%d] %s.",
  52.             P->Line, P->Src, Seg->Line, BP->Src
  53.          );
  54.       if (IP != 0 && Seg->Base + Seg->Size > IP->Base)
  55.          FATAL("Overlapping segments at [%d] %s and [%d] %s.",
  56.             Seg->Line, BP->Src, IP->Line, IP->Src
  57.          );
  58.       NewI = FormImage(
  59.          Seg->Base, Seg->Size, BP->Src, BP->Obj, Seg->Line, Seg->Loc
  60.       );
  61.       if (P == 0) IHead = NewI; else P->Next = NewI;
  62.       if (IP == 0) ITail = NewI; else IP->Prev = NewI;
  63.       NewI->Next = IP, NewI->Prev = P;
  64.    }
  65. }
  66.  
  67. static void FitGap(Gap G) {
  68.    Image P, IP, NewI; long End, EndP;
  69.    word Base = G->Seg->Base + G->Offset; long Size = G->Size;
  70.    for (IP = IHead; IP != 0; IP = IP->Next)
  71.       if (IP->Base > Base) break;
  72.    P = (IP == 0)? ITail: IP->Prev;
  73.    if (P == 0) FATAL("Internal error (2).");
  74.    End = Base + Size, EndP = P->Base + P->Size;
  75.    if (EndP < End) FATAL("Internal error (3).");
  76.    if (P->Base < Base) {
  77.       P->Size = Base - P->Base;
  78.       if (EndP > End) {
  79.          NewI = FormImage(
  80.             (word)End, EndP - End, P->Src, P->Obj, P->Line, P->Loc + P->Size
  81.          );
  82.          NewI->Next = IP, P->Next = NewI;
  83.          NewI->Prev = P;
  84.          if (IP == 0) ITail = NewI; else IP->Prev = NewI;
  85.       }
  86.    } else if (EndP > End) P->Base += Size, P->Size -= Size;
  87.    else {
  88.       if (P->Prev == 0) IHead = P->Next; else P->Prev->Next = P->Next;
  89.       if (P->Next == 0) ITail = P->Prev; else P->Next->Prev = P->Prev;
  90.       free(P);
  91.    }
  92. }
  93.  
  94. typedef struct Free *Free;
  95. struct Free {
  96.    word Base; long Size; Block BP;
  97. };
  98. static Free *FHead;
  99. static int *FSize;
  100.  
  101. void SetFree(void) {
  102.    int T;
  103.    FHead = (Free *)Allocate(SEG_TYPES * sizeof *FHead);
  104.    FSize = (int *)Allocate(SEG_TYPES * sizeof *FSize);
  105.    for (T = 0; T < SEG_TYPES; T++) {
  106.       Block P, B; Free F; long Base;
  107.       FHead[T] = (Free)Allocate((BSize[T] + 1) * sizeof *FHead[T]);
  108.       for (P = 0, B = BHead[T], F = FHead[T]; B != 0; P = B, B = B->Next) {
  109.          Base = (P == 0)? AddrTab[T].Lo: (long) P->Seg->Base + P->Seg->Size;
  110.          if (Base >= B->Seg->Base) continue;
  111.          F->Base = Base, F->Size = (long)B->Seg->Base - Base, F->BP = P, F++;
  112.       }
  113.       Base = (P == 0)? AddrTab[T].Lo: (long) P->Seg->Base + P->Seg->Size;
  114.       if (Base <= AddrTab[T].Hi)
  115.          F->Base = Base, F->Size = (long)AddrTab[T].Hi + 1 - Base,
  116.          F->BP = P, F++;
  117.       FSize[T] = F - FHead[T];
  118.    }
  119. }
  120.  
  121. void PurgeFree(void) {
  122.    int T;
  123.    for (T = 0; T < SEG_TYPES; T++) free(FHead[T]);
  124.    free(FHead), free(FSize);
  125. }
  126.  
  127. void BestFit(char *Obj, Segment Seg) {
  128.    byte T = Seg->Type; Free Best, FP; Block B;
  129.    if (!Seg->Rel) return;
  130.    StartLine = Seg->Line, StartF = Seg->File;
  131.    for (Best = 0, FP = FHead[T]; FP < FHead[T] + FSize[T]; FP++) {
  132.       if (
  133.          Seg->Size <= FP->Size && (Best == 0 || FP->Size < Best->Size)
  134.       ) Best = FP;
  135.    }
  136.    if (Best == 0) FATAL("Cannot fit segment.");
  137.    B = (Block)Allocate(sizeof *B);
  138.    B->Seg = Seg, B->Src = FileTab[StartF], B->Obj = Obj;
  139.    if (Best->BP == 0)
  140.       B->Next = BHead[T], BHead[T] = B;
  141.    else
  142.       B->Next = Best->BP->Next, Best->BP->Next = B;
  143.    Seg->Rel = 0, Seg->Base = Best->Base,
  144.    Best->BP = B, Best->Base += Seg->Size, Best->Size -= Seg->Size;
  145. }
  146.  
  147. void FitSegs(FileBuf F) {
  148.    int S; Segment Seg;
  149.    FileTab = F->File;
  150.    for (S = TYPES; S < F->Segs; S++) {
  151.       Seg = F->Seg + S - TYPES, BestFit(F->Name, Seg);
  152.    }
  153. }
  154.  
  155. void SetSeg(void) {
  156.    Segment S; int I;
  157.    USeg = (Segment)Allocate(TYPES * sizeof *USeg);
  158.    for (S = USeg; S < USeg + TYPES; S++)
  159.       S->Line = S->File = 0, S->Rel = 0, S->Type = S - USeg,
  160.       S->Base = 0, S->Size = 0, S->Loc = 0L;
  161.    BHead = (Block *)Allocate(SEG_TYPES * sizeof *BHead);
  162.    BSize = (int *)Allocate(SEG_TYPES * sizeof *BSize);
  163.    for (I = 0; I < SEG_TYPES; I++) BHead[I] = 0, BSize[I] = 0;
  164. }
  165.  
  166. void FreeBlocks(void) {
  167.    int I;
  168.    for (I = 0; I < SEG_TYPES; I++) {
  169.       Block B, N;
  170.       for (B = BHead[I]; B != 0; B = N) N = B->Next, free(B);
  171.    }
  172.    free(BHead), free(BSize);
  173. }
  174.  
  175. void Fit(char *Obj, Segment Seg) {
  176.    byte T = Seg->Type; Block Cur, Prev, B;
  177.    if (Seg->Rel) return;
  178.    for (Prev = 0, Cur = BHead[T]; Cur != 0; Prev = Cur, Cur = Cur->Next)
  179.       if (Cur->Seg->Base >= Seg->Base) break;
  180.    if (Prev != 0 && Prev->Seg->Base + Prev->Seg->Size > Seg->Base)
  181.       ERROR("Overlapping segments: %s [%d] and %s [%d].",
  182.          FileTab[Seg->File], Seg->Line, Prev->Src, Prev->Seg->Line
  183.       );
  184.    if (Cur != 0 && Cur->Seg->Base < Seg->Base + Seg->Size)
  185.       ERROR("Overlapping segments: %s [%d] and %s [%d].",
  186.          FileTab[Seg->File], Seg->Line, Cur->Src, Cur->Seg->Line
  187.       );
  188.    B = (Block)Allocate(sizeof *B);
  189.    B->Src = FileTab[Seg->File], B->Obj = Obj, B->Seg = Seg, B->Next = Cur;
  190.    if (Prev == 0) BHead[T] = B; else Prev->Next = B;
  191.    BSize[T]++;
  192. }
  193.  
  194. void GetHead(FileBuf F) {
  195.    word MAGIC; long S; byte Buf[0x100];
  196.    FILE *FP = fopen(F->Name, "rb+");
  197.    if (FP == 0) FATAL("Cannot open %s.", F->Name);
  198.    MAGIC = GetW(FP);
  199.    if (MAGIC != 0x55aa) FATAL("Invalid object file %s.", F->Name);
  200.    F->Loc = GetL(FP),
  201.    F->Files = GetL(FP), F->Segs = GetL(FP),
  202.    F->Gaps = GetL(FP), F->Syms = GetL(FP),
  203.    F->Exps = GetL(FP), F->Relocs = GetL(FP);
  204.    S = F->Loc + F->Files + F->Segs + F->Gaps + F->Syms + F->Exps + F->Relocs;
  205.    if (GetL(FP) != S&0xffffffff) FATAL("Corrupt object file %s.", F->Name);
  206.    F->File = (char **)Allocate((word)F->Files * sizeof *F->File);
  207.    F->Seg = (F->Segs < TYPES)? 0: (Segment)Allocate((word)(F->Segs - TYPES) * sizeof *F->Seg);
  208.    F->G = (Gap)Allocate((word)F->Gaps * sizeof *F->G);
  209.    F->Sym = (Symbol *)Allocate((word)F->Syms * sizeof *F->Sym);
  210.    FileTab = F->File;
  211.    fseek(FP, F->Loc, SEEK_SET);
  212.    for (S = 0; S < F->Files; S++) {
  213.       word L;
  214.       L = GetW(FP), fread(Buf, 1, L, FP), Buf[L] = '\0';
  215.       F->File[S] = CopyS(Buf);
  216.    }
  217.    for (S = TYPES; S < F->Segs; S++) {
  218.       Segment Seg = F->Seg + S - TYPES; word U;
  219.       Seg->Line = GetW(FP), Seg->File = GetW(FP),
  220.       U = GetW(FP), Seg->Size = GetW(FP),
  221.       Seg->Base = GetW(FP), Seg->Loc = GetL(FP);
  222.       Seg->Rel = (U >> 8)&1, Seg->Type = U&0xff;
  223.       Fit(F->Name, Seg);
  224.    }
  225.    for (S = 0; S < F->Gaps; S++) {
  226.       Gap G = F->G + S; word Sg;
  227.       Sg = GetW(FP), G->Offset = GetW(FP), G->Size = GetW(FP);
  228.       G->Seg = Sg < TYPES? &USeg[Sg]: &F->Seg[Sg - TYPES];
  229.    }
  230.    for (S = 0; S < F->Syms; S++) {
  231.       Symbol Sym; byte B, Defined, Global, Address; word U, L, Offset;
  232.       B = GetB(FP), U = GetW(FP), Offset = GetW(FP),
  233.       L = GetW(FP);
  234.       if (L > 0) fread(Buf, 1, L, FP);
  235.       Buf[L] = '\0';
  236.       Global = (B&8)? 1: 0, Defined = (B&4)? 1: 0, Address = (B&2)? 1: 0;
  237.       if (!Global) {
  238.          Sym = (Symbol)Allocate(sizeof *Sym);
  239.          Sym->Variable = 0, Sym->Address = Address;
  240.          Sym->Global = Global, Sym->Defined = Defined;
  241.          Sym->Seg = !Address? 0: U < TYPES? &USeg[U]: &F->Seg[U - TYPES];
  242.          Sym->Offset = Offset;
  243.          Sym->Index = F - FTab;
  244.          Sym->Name = CopyS(Buf);
  245.       } else {
  246.          Sym = LookUp(Buf);
  247.          if (Sym->Defined && Defined)
  248.             ERROR("Symbol %s redefined: %s %s.",
  249.                Sym->Name, FTab[Sym->Index].Name, F->Name
  250.             );
  251.          else {
  252.             if (Sym->Address) {
  253.                Segment Seg = U < TYPES? &USeg[U]: &F->Seg[U - TYPES];
  254.                if (!Address)
  255.                   ERROR("Address %s redeclared as number: %s %s",
  256.                      Sym->Name, FTab[Sym->Index].Name, F->Name
  257.                   );
  258.                else if (Sym->Seg->Type != Seg->Type)
  259.                   ERROR("Type mismatch %s: %s %s",
  260.                      Sym->Name, FTab[Sym->Index].Name, F->Name
  261.                   );
  262.             } else if (Address && Sym->Global)
  263.                ERROR("Number %s redeclared as address: %s %s",
  264.                   Sym->Name, FTab[Sym->Index].Name, F->Name
  265.                );
  266.             if (Defined || !Sym->Global) {
  267.                Sym->Variable = 0, Sym->Address = Address;
  268.                Sym->Global = Global, Sym->Defined = Defined;
  269.                Sym->Seg = !Address? 0: U < TYPES? &USeg[U]: &F->Seg[U - TYPES],
  270.                Sym->Offset = Offset;
  271.                Sym->Index = F - FTab;
  272.             }
  273.          }
  274.       }
  275.       F->Sym[S] = Sym;
  276.    }
  277.    F->Loc = ftell(FP);
  278.    fclose(FP);
  279. }
  280.  
  281. typedef struct RList *RList;
  282. struct RList {
  283.    byte Size; long PC, Val; RList Next;
  284. };
  285. RList RHead;
  286.  
  287. void AddReloc(byte Size, long PC, long Val) {
  288.    RList R = Allocate(sizeof *R), P, S;
  289.    for (P = 0, S = RHead; S != 0; P = S, S = S->Next)
  290.       if (S->PC >= PC) break;
  291.    if (S != 0 && S->PC == PC) FATAL("Internal error (4)."); 
  292.    if (P == 0) RHead = R; else P->Next = R;
  293.    R->Next = S,
  294.    R->Size = Size, R->PC = PC, R->Val = Val;
  295. }
  296.  
  297. void SetRelocs(FileBuf F) {
  298.    long S; struct Item IBuf; Exp E, NextE;
  299.    FILE *FP = fopen(F->Name, "rb+");
  300.    if (FP == 0) FATAL("Cannot open %s.", F->Name);
  301.    FileTab = F->File; fseek(FP, F->Loc, SEEK_SET);
  302.    ExpBuf = (Exp *)Allocate((unsigned)F->Exps * sizeof *ExpBuf);
  303.    ExpInit();
  304.    for (S = 0; S < F->Exps; S++) {
  305.       Exp *EP = ExpBuf + S; byte Tag; Segment Seg; Exp A, B, C;
  306.       word Line, File, U, Offset; byte Op;
  307.       StartLine = GetW(FP), StartF = GetW(FP), Tag = GetB(FP);
  308.       switch (Tag) {
  309.          case NumX:
  310.             Value = GetW(FP); *EP = MakeExp(NumX, Value);
  311.          break;
  312.          case AddrX:
  313.             U = GetW(FP), Offset = GetW(FP);
  314.             Seg = U < TYPES? &USeg[U]: &F->Seg[U - TYPES];
  315.             *EP = MakeExp(AddrX, Seg, Offset);
  316.          break;
  317.          case SymX:
  318.             U = GetW(FP); *EP = MakeExp(SymX, F->Sym[U]);
  319.          break;
  320.          case UnX:
  321.             Op = GetB(FP),
  322.             U = GetW(FP), A = ExpBuf[U],
  323.             *EP = MakeExp(UnX, Op, A);
  324.          break;
  325.          case BinX:
  326.             Op = GetB(FP),
  327.             U = GetW(FP), A = ExpBuf[U],
  328.             U = GetW(FP), B = ExpBuf[U],
  329.             *EP = MakeExp(BinX, Op, A, B);
  330.          break;
  331.          case CondX:
  332.             U = GetW(FP), A = ExpBuf[U],
  333.             U = GetW(FP), B = ExpBuf[U],
  334.             U = GetW(FP), C = ExpBuf[U],
  335.             *EP = MakeExp(CondX, A, B, C);
  336.          break;
  337.       }
  338.    }
  339.    for (S = 0; S < F->Relocs; S++) {
  340.       word U, PC;
  341.       IBuf.Line = GetW(FP), IBuf.File = GetW(FP),
  342.       IBuf.Tag = GetB(FP),
  343.       U = GetW(FP), IBuf.E = ExpBuf[U],
  344.       U = GetW(FP), IBuf.Seg = U < TYPES? &USeg[U]: &F->Seg[U - TYPES];
  345.       IBuf.Offset = GetW(FP);
  346.       Resolve(&IBuf);
  347.       PC = (long)IBuf.Seg->Base + (long)IBuf.Offset;
  348.       switch (IBuf.Tag) {
  349.          case 'b': AddReloc(1, PC, LVal); break;
  350.          case 'w': AddReloc(2, PC, LVal); break;
  351.          default: FATAL("Internal error (5).");
  352.       }
  353.    }
  354.    fclose(FP);
  355.    for (E = ExpHead; E != 0; E = NextE) NextE = E->Next, free(E);
  356.    free(ExpBuf);
  357. }
  358.  
  359. /* HEX OUTPUT ROUTINES */
  360. FILE *OutF = 0;
  361. byte HexBuf[0x10]; int HexX;
  362. long HexAddr;
  363. void OpenHex(char *Hex) {
  364.    OutF = fopen(Hex, "w");
  365.    if (OutF == 0) FATAL("Cannot open output file.");
  366.    HexX = 0;
  367. }
  368. void EndHex(void) {
  369.    if (HexX > 0) {
  370.       int H, Sum;
  371.       Sum = (HexAddr&0xff) + ((HexAddr >> 8)&0xff) + HexX;
  372.       fprintf(OutF, ":%02X%04X00", HexX, HexAddr);
  373.       for (H = 0; H < HexX; H++)
  374.          fprintf(OutF, "%02X", HexBuf[H]), Sum += HexBuf[H];
  375.       fprintf(OutF, "%02X\n", (-Sum)&0xff);
  376.       HexX = 0;
  377.    }
  378. }
  379. void PutHex(long Addr, byte Hex) {
  380.    if (HexX == 0) HexAddr = Addr;
  381.    HexBuf[HexX++] = Hex;
  382.    if (HexX == 0x10) {
  383.       int H, Sum;
  384.       Sum = (HexAddr&0xff) + ((HexAddr >> 8)&0xff) + HexX;
  385.       fprintf(OutF, ":10%04X00", HexAddr);
  386.       for (H = 0; H < HexX; H++)
  387.          fprintf(OutF, "%02X", HexBuf[H]), Sum += HexBuf[H];
  388.       fprintf(OutF, "%02X\n", (-Sum)&0xff);
  389.       HexX = 0;
  390.    }
  391. }
  392. void CloseHex(void) {
  393.    EndHex();
  394.    fprintf(OutF, ":00000001FF\n");
  395.    fclose(OutF);
  396. }
  397.  
  398. void GenImage(char *Hex) {
  399.    Image IP; RList R; FILE *FP; char *File;
  400.    FP = 0, File = 0;
  401.    OpenHex(Hex);
  402.    for (IP = IHead, R = RHead; IP != 0; IP = IP->Next) {
  403.       long Addr;
  404.       if (IP->Obj != File) {
  405.          if (FP != 0) fclose(FP), FP = 0;
  406.          FP = fopen(IP->Obj, "rb+");
  407.          if (FP == 0) FATAL("Cannot open %s.", IP->Obj);
  408.       }
  409.       fseek(FP, IP->Loc, SEEK_SET);
  410.       for (Addr = IP->Base; Addr < IP->Base + IP->Size; ) {
  411.          if (R != 0 && R->PC < Addr) FATAL("Internal error (6).");
  412.          if (R != 0 && R->PC == Addr) {
  413.             switch (R->Size) {
  414.                case 1: fgetc(FP); PutHex(Addr++, (byte)(R->Val&0xff)); break;
  415.                case 2:
  416.                   fgetc(FP), fgetc(FP);
  417.                   PutHex(Addr++, (byte)((R->Val >> 8)&0xff)),
  418.                   PutHex(Addr++, (byte)(R->Val&0xff));
  419.                break;
  420.                default: FATAL("Internal error (7).");
  421.             }
  422.             R = R->Next;
  423.          } else {
  424.             int Ch = fgetc(FP);
  425.             if (Ch == EOF) FATAL("Internal error (8).");
  426.             PutHex(Addr++, (byte)(Ch&0xff));
  427.          }
  428.       }
  429.       if (IP->Next != 0 && IP->Base + IP->Size < IP->Next->Base) EndHex();
  430.    }
  431.    CloseHex();
  432. }
  433.  
  434. void Link(char *Hex) {
  435.    int A;
  436.    Active = 1, Phase = 2;
  437.    SymInit(); SetSeg();
  438.    for (A = 0; A < Fs; A++) GetHead(FTab + A);
  439.    for (Sym = NIL->Next[0]; Sym != NIL; Sym = Sym->Next[0])
  440.       if (!Sym->Defined) ERROR("Unresolved external: %s.", Sym->Name);
  441.    CHECK();
  442.    InSeg = 1;
  443.    SetFree();
  444.    for (A = 0; A < Fs; A++) FitSegs(FTab + A);
  445.    PurgeFree();
  446.    InSeg = 0;
  447.    CHECK();
  448.    SetImage();
  449.    for (A = 0; A < Fs; A++) {
  450.       Gap G; FileBuf F = FTab + A;
  451.       for (G = F->G; G < F->G + F->Gaps; G++) FitGap(G);
  452.    }
  453.    CHECK();
  454.    FreeBlocks();
  455.    InSeg = 1; RHead = 0;
  456.    for (A = 0; A < Fs; A++) SetRelocs(FTab + A);
  457.    InSeg = 0;
  458.    CHECK();
  459.    GenImage(Hex);
  460. }
  461.